package baseclass.a_sort.heapSort;


import baseclass.a_sort.ArraysTool;

import java.util.Arrays;

/**
 * @date 2020/2/26 22:32
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {9, 2, 3, 1, -4};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void heapSort(int[] arr) {
        if (!ArraysTool.check(arr)) return;
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        while (heapSize > 0) {
            ArraysTool.swap(arr, 0, --heapSize);
            heapify(arr, heapSize);
        }
    }

    /**
     * 构造大跟堆
     *
     * @param arr
     * @param i
     */
    public static void heapInsert(int[] arr, int i) {
        int parent = (i - 1) / 2;
        while (arr[i] > arr[parent]) {
            ArraysTool.swap(arr, parent, i);
            i = parent;
            parent = (i - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int heapSize) {
        int parent = 0;
        int left = 1;
        int right = 2;
        int largest;
        //首先要有左孩子
        while (left < heapSize) {
            //判断是否有右孩子，并取左右孩子中的较大者
            if (right < heapSize) {
                largest = arr[left] > arr[right] ? left : right;
            } else {
                largest = left;
            }
            //父比左右大，不用调堆
            if (arr[parent] >= arr[largest]) break;
            ArraysTool.swap(arr, parent, largest);
            parent = largest;
            left = 2 * parent + 1;
            right = left + 1;
        }
    }
}
